//题目:
// 给定两个以字符串形式表示的非负整数num1和num2，返回num1和num2的乘积，它们的乘积也表示为字符串形式。
// 注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;
//代码:
class Solution {
public:
    void addret(string& base,string tmp,int i)
    {
        //  1368   8631
        //  912     219
        //从ret从左往右的第i位开始加tmp
        if(base==""){ base=tmp; return;}
        int result=0,cur=0;
        string ret=base.substr(0,i);
        while(cur<tmp.size() || result)
        {
            if(i<base.size() )
                result+=base[i++]-'0';
            if(cur<tmp.size())
                result+=tmp[cur++]-'0';
            ret+=result%10+'0';
            result/=10;
        }
        base=ret;
    }
    string multiply(string num1, string num2)
    {
        if (num1 == "0" || num2 == "0")return "0";
        string ret;
        int cur1=num1.size()-1,cur2=num2.size()-1,result=0,pos=0;
        while(cur1>=0)
        {
            cur2=num2.size()-1;
            string tmp;//计算num1一位的结果
            while(cur2>=0 && result>0)
            {
                result+=(num1[cur1]-'0')*(num2[cur2--]-'0');
                tmp+=result%10+'0';
                result/=10;
            }
            //cout<<" "<<tmp<<endl;
            //  1368   8631
            //  912     219
            //         88401
            //           654
            //2.将计算结果加到ret上，注意错位
            addret(ret,tmp,pos++);
            cur1--;
        }
        reverse(ret.begin(),ret.end());
        return ret;
    }
};